/**
 * 每次你可以爬 1 或 2 个台阶
 * 爬到 n 阶需要几步
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  var a = [];
  a[0] = 1, a[1] = 1;
  for (var i = 2; i <= n; i++)
    a[i] = a[i - 1] + a[i - 2];
  return a[n];
};

console.log(climbStairs(5))

/**
 * 一次可以跳 1 阶，2 阶或者 3 阶，如果想跳上一个 N 阶共有几种跳法：
 * 假设青蛙跳上一个n级的台阶总共有f(n)种跳法。
 * 现在青蛙从第n个台阶往下跳，它可以跳到任意一个台阶上，所以：
 * f(n)=f(n-1)+f(n-2)+...+f(1)
 * f(n-1)=f(n-2)+f(n-3)+...f(1)
 * 将f(n-2)+...+f(1)替换为f(n-2)
 * f(n)=2f(n-1)
 * @param {*} number 
 * @returns 
 */
function jumpFloorII(number) {
  if (number == 1) {
    return 1;
  } else {
    return 2 * jumpFloorII(number - 1);
  }
}

console.log(jumpFloorII(5))